package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/distribute-coins-in-binary-tree/description/
 * @create 2025/9/26 13:49
 * @since JDK17
 */

public class Solution63 {
    int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[] { 0, 0, 0 };
        }
        int cnt = 1, cost = 0, coin = 0;
        var l = dfs(root.left);
        var r = dfs(root.right);
        cnt += l[0] + r[0]; // 结点树
        coin = root.val + l[1] + r[1]; // 币数
        cost = Math.abs(l[0] - l[1]) + Math.abs(r[0] - r[1]) + l[2] + r[2];
        return new int[] { cnt, coin, cost };
    }

    public int distributeCoins(TreeNode root) {
        return dfs(root)[2];
    }
}
